package sort;

/**
 * @author huangxin
 * @date 2019/6/25-11:18
 */
public class MergeSort {
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }


    public static void mergeSort(int[] arr, int low, int high) {

        int mid = (low + high) / 2;
        if (low < high) {
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, index = 0;

        while (i <= mid && j <= high) {
            temp[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }


        while (i <= mid) {
            temp[index++] = arr[i++];
        }

        while (j <= high) {
            temp[index++] = arr[j++];
        }

        for (int k = low; k <= high; k++) {
            arr[k] = temp[k - low];
        }
    }
}
